<p>  在弄懂什么是缓存淘汰算法之前，我们先来想想一下几个问题：</p>
<p>1、为什么需要缓存？<br>  比如我们需要通过Ajax从服务器获取某些数据、信息的时候，那么这个获取数据所花费的时间是不是比我们从内存里面读取数据慢得多呢？又或者，当我们需要从磁盘中读取文件的时候，这些操作所花费的时间是不是比我们读取内存中的数据的时间更久呢？答案应该是肯定的，因为硬盘的读取速度比缓存更慢，而从服务器获取数据更是要花费网络连接、服务器收发数据、处理信息、甚至从数据库读取数据等时间；如果这些数据是需要我们实时获取的也就只能按部就班的进行了，但是如果这些数据其实不比实时获取的呢？那么我们可不可以在第一次获取到数据后将数据缓存在内存里面呢?然后下次再从内存里面取出这些数据，是不是比起从服务器或者硬盘里面读取更快呢？</p>
<p>2、为什么要淘汰缓存<br>  因为我们的设备的内存是有限的，不管是客户端还是服务器的设备，都不可能不断的将数据存入内存中而不删除。我们要做到就是通过淘汰算法让存入内存中的数据能发挥最大价值。</p>
<p>3、常用的缓存淘汰算法<br>FIFO 、LRU、LFU缓存算法算是比较简单的，它们的区别是当缓存空间满的时候，其对数据淘汰策略不同而已。</p>
<h4 id="FIFO（First Input First Output，先进先出）"><a href="#FIFO（First Input First Output，先进先出）">FIFO（First Input First Output，先进先出）</a></h4><p>  先进先出淘汰算法，很容易理解，核心原则是：先进行缓存的数据先淘汰掉。</p>
<table>
<thead>
<tr>
<th>维度</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>命中率</td>
<td>低</td>
</tr>
<tr>
<td>复杂度</td>
<td>简单</td>
</tr>
<tr>
<td>存储成本</td>
<td>低</td>
</tr>
<tr>
<td>缺陷</td>
<td>速度快，但使用价值不高</td>
</tr>
</tbody></table>
<h4 id="LRU（Least Recently Used，最近最少使用）"><a href="#LRU（Least Recently Used，最近最少使用）">LRU（Least Recently Used，最近最少使用）</a></h4><p>  最近最少使用:根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。</p>
<table>
<thead>
<tr>
<th>维度</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>命中率</td>
<td>当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。</td>
</tr>
<tr>
<td>复杂度</td>
<td>较简单</td>
</tr>
<tr>
<td>存储成本</td>
<td>一般</td>
</tr>
<tr>
<td>缺陷</td>
<td>速度较慢；仅从时间上考虑，没有考虑频率</td>
</tr>
</tbody></table>
<h4 id="LFU（Least Frequently Used，最不经常使用）"><a href="#LFU（Least Frequently Used，最不经常使用）">LFU（Least Frequently Used，最不经常使用）</a></h4><p>  最不经常使用：算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。</p>
<table>
<thead>
<tr>
<th>维度</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>命中率</td>
<td>一般情况下，LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录，一旦数据访问模式改变，LFU需要更长时间来适用新的访问模式，即：LFU存在历史数据影响将来数据的“缓存污染”效用。</td>
</tr>
<tr>
<td>复杂度</td>
<td>需要维护一个队列记录所有数据的访问记录，每个数据都需要维护引用计数。</td>
</tr>
<tr>
<td>存储成本</td>
<td>需要记录所有数据的访问记录，内存消耗较高；需要基于引用计数排序，性能消耗较高。</td>
</tr>
<tr>
<td>缺陷</td>
<td>仅考虑频率</td>
</tr>
</tbody></table>
<ol start="3">
<li>LRU-K<br>3.1. 原理</li></ol>
<p>LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。</p>
<p>3.2. 实现</p>
<p>相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下：</p>
<ol>
<li><p>数据第一次被访问，加入到访问历史列表；</p>
</li><li><p>如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；</p>
</li><li><p>当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；</p>
</li><li><p>缓存数据队列中被再次访问后，重新排序；</p>
</li><li><p>需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。</p>
</li></ol>
<p>LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。</p>
<p>3.3. 分析</p>
<p>【命中率】</p>
<p>LRU-K降低了“缓存污染”带来的问题，命中率比LRU要高。</p>
<p>【复杂度】</p>
<p>LRU-K队列是一个优先级队列，算法复杂度和代价比较高。</p>
<p>【代价】</p>
<p>由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象，因此内存消耗会比LRU要多；当数据量很大的时候，内存消耗会比较可观。</p>
<p>LRU-K需要基于时间进行排序（可以需要淘汰时再排序，也可以即时排序），CPU消耗比LRU要高。</p>
<p>  TwoQueues：FIFO+ LRU，FIFO主要存放初次存入的数据，LRU中存放至少使用过两次的热点数据，此算法命中率高，适应性强，复杂度低。</p>
<p>他淘汰算法还有很多很多，但实际用的比较多的也就这两种。因为他们本身算法不复杂，容易实现，执行效率高，缓存的命中率在大多数场合也还可以接受。毕竟缓存算法也是需要消耗CPU的，如果太过复杂，虽然命中率有所提高，但得不偿失。试想一下，如果从缓存中取数据，比从原始位置取还消耗时间，要缓存何用？</p>
<pre><code><span class="code-block"> 具体理论就不多说了，网上有的是，我也不怎么懂，今天给大家分享的是JavaScript版的TwoQueues缓存模型。

 还是先说说使用方法，很简单。</span>
</code><span class="copy-button">复制代码</span></pre>
<p>最后，再次提醒，缓存算法需要和实际应用场景相结合，没有万能算法，合适的才是最好的！</p>
